/*
 * @lc app=leetcode.cn id=24 lang=cpp
 * @lcpr version=30204
 *
 * [24] 两两交换链表中的节点
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x, next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x, next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        // ListNode dummy(0, head);
        // ListNode *prevgroup = &dummy;

        // while (prevgroup->next && prevgroup->next->next)
        // {
        //     ListNode *first = prevgroup->next;
        //     ListNode *second = first->next;

        //     // Swap the two nodes
        //     first->next = second->next;
        //     second->next = first;
        //     prevgroup->next = second;

        //     // Move to the next pair
        //     prevgroup = first;
        // }

        // return dummy.next;
        return reverseKGroup(head, 2);
    }

    ListNode *reverseKGroup(ListNode *head, int k)
    {
        ListNode dummy(0, head);
        ListNode *prevgroup = &dummy;

        while (true)
        {
            // 检查是否还有足够的节点能够翻转
            ListNode *groupend = prevgroup;
            for (int i = 0; i < k; ++i)
            {
                groupend = groupend->next;
                if (!groupend)
                    return dummy.next; // Not enough nodes to reverse
            }

            // 反转K个节点
            ListNode *cur = prevgroup->next;
            ListNode *prev = nullptr;
            ListNode *next = nullptr;
            for (int i = 0; i < k; ++i)
            {
                next = cur->next;
                cur->next = prev;
                prev = cur;
                cur = next;
            }

            // 结束后cur为下一组的头结点，prev为当前组的最后一个节点
            ListNode *groupstart = prevgroup->next; // 当前组的头结点为前一组的下一个节点
            groupstart->next = cur;                 // 当前组的头结点连接下一个组的头结点
            prevgroup->next = prev;                 // 前一组的尾节点连接当前组的尾节点

            prevgroup = groupstart; // 这一组完了，迭代前一组的尾节点
        }

        return dummy.next;
    }
};
// @lc code=end

/*
// @lcpr case=start
// [1,2,3,4]\n
// @lcpr case=end

// @lcpr case=start
// []\n
// @lcpr case=end

// @lcpr case=start
// [1]\n
// @lcpr case=end

 */
